SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Directed graph</title>

</head>

Directed graph

</h1>

</header>

In <a href="Mathematics" title="Mathematics">mathematics</a>, and more specifically in <a href="Graph_theory" title="Graph theory">graph theory</a>, a directed graph (or digraph) is a <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> that is made up of a set of <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertices</a> connected by directed <a href="Edge_(graph_theory)" class="mw-redirect" title="Edge (graph theory)">edges</a>, often called arcs.

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

In formal terms, a directed graph is an ordered pair G = (V, A) where<a href="#cite_note-1">[1]</a>

<ul><li>V is a <a href="Set_(mathematics)" title="Set (mathematics)">set</a> whose <a href="Element_(mathematics)" title="Element (mathematics)">elements</a> are called <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertices</a>, nodes, or points;</li>

<li>A is a set of <a href="Ordered_pair" title="Ordered pair">ordered pairs</a> of vertices, called arcs, directed edges (sometimes simply edges with the corresponding set named E instead of A), arrows, or directed lines.</li></ul>

It differs from an ordinary or <a href="Undirected_graph" class="mw-redirect" title="Undirected graph">undirected graph</a>, in that the latter is defined in terms of <a href="Unordered_pair" title="Unordered pair">unordered pairs</a> of vertices, which are usually called edges, links or lines.

The aforementioned definition does not allow a directed graph to have multiple arrows with the same source and target nodes, but some authors consider a broader definition that allows directed graphs to have such multiple arcs (namely, they allow the arc set to be a <a href="Multiset" title="Multiset">multiset</a>). Sometimes these entities are called <a href="Directed_multigraph" class="mw-redirect" title="Directed multigraph">directed multigraphs</a> (or multidigraphs).

On the other hand, the aforementioned definition allows a directed graph to have <a href="Loop_(graph_theory)" title="Loop (graph theory)">loops</a> (that is, arcs that directly connect nodes with themselves), but some authors consider a narrower definition that does not allow directed graphs to have loops.<a href="#cite_note-Chartrand-2">[2]</a>

Directed graphs without loops may be called simple directed graphs, while directed graphs with loops may be called loop-digraphs (see section <a href="#Types_of_directed_graphs">Types of directed graph</a>).

<div class="mw-heading mw-heading2"><h2 id="Types_of_directed_graphs">Types of directed graphs</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">See also: <a href="Graph_(discrete_mathematics)#Types_of_graphs" title="Graph (discrete mathematics)">Graph (discrete mathematics) § Types of graphs</a></div>

<div class="mw-heading mw-heading3"><h3 id="Subclasses">Subclasses</h3></div>

<ul><li>Symmetric directed graphs are directed graphs where all edges appear twice, one in each direction (that is, for every arrow that belongs to the digraph, the corresponding inverse arrow also belongs to it). (Such an edge is sometimes called "bidirected" and such graphs are sometimes called "bidirected", but this conflicts with the meaning for <a href="Bidirected_graph" title="Bidirected graph">bidirected graphs</a>.)</li>

<li>Simple directed graphs are directed graphs that have no <a href="Loop_(graph_theory)" title="Loop (graph theory)">loops</a> (arrows that directly connect vertices to themselves) and no multiple arrows with same source and target nodes. As already introduced, in case of multiple arrows the entity is usually addressed as <a href="Directed_multigraph" class="mw-redirect" title="Directed multigraph">directed multigraph</a>. Some authors describe digraphs with loops as loop-digraphs.<a href="#cite_note-Chartrand-2">[2]</a>

<ul><li>Complete directed graphs are simple directed graphs where each pair of vertices is joined by a symmetric pair of directed arcs (it is equivalent to an undirected <a href="Complete_graph" title="Complete graph">complete graph</a> with the edges replaced by pairs of inverse arcs). It follows that a complete digraph is symmetric.</li>

<li>Semicomplete multipartite digraphs are simple digraphs in which the vertex set is partitioned into sets such that for every pair of vertices x and y in different sets, there is an arc between x and y. There can be one arc between x and y or two arcs in opposite directions.<a href="#cite_note-3">[3]</a></li>

<li>Semicomplete digraphs are simple digraphs where there is an arc between each pair of vertices. Every semicomplete digraph is a semicomplete multipartite digraph in a trivial way, with each vertex constituting a set of the partition.<a href="#cite_note-Bang-Jensen_2018-4">[4]</a></li>

<li>Quasi-transitive digraphs are simple digraphs where for every triple x, y, z of distinct vertices with arcs from x to y and from y to z, there is an arc between x and z. There can be just one arc between x and z or two arcs in opposite directions. A semicomplete digraph is a quasi-transitive digraph. There are extensions of quasi-transitive digraphs called k-quasi-transitive digraphs.<a href="#cite_note-5">[5]</a></li>

<li><a href="Oriented_graph" class="mw-redirect" title="Oriented graph">Oriented graphs</a> are directed graphs having no opposite pairs of directed edges (i.e. at most one of (x, y) and (y, x) may be arrows of the graph). It follows that a directed graph is an oriented graph if and only if it has no <a href="Directed_cycle" class="mw-redirect" title="Directed cycle">2-cycle</a>.<a href="#cite_note-6">[6]</a> Such a graph can be obtained by applying an <a href="Orientation_(graph_theory)" title="Orientation (graph theory)">orientation</a> to an undirected graph.

<ul><li><a href="Tournament_(mathematics)" class="mw-redirect" title="Tournament (mathematics)">Tournaments</a> are oriented graphs obtained by choosing a direction for each edge in undirected <a href="Complete_graph" title="Complete graph">complete graphs</a>. A tournament is a semicomplete digraph.<a href="#cite_note-Bang-Jensen_2018-4">[4]</a></li>

<li>A directed graph is acyclic if it has no <a href="Directed_cycle" class="mw-redirect" title="Directed cycle">directed cycles</a>. The usual name for such a digraph is <a href="Directed_acyclic_graph" title="Directed acyclic graph">directed acyclic graph</a> (DAG).<a href="#cite_note-7">[7]</a>

<ul><li><a href="Multitree" title="Multitree">Multitrees</a> are DAGs in which there are no two distinct directed paths from the same starting vertex to the same ending vertex.</li>

<li><a href="Oriented_tree" class="mw-redirect" title="Oriented tree">Oriented trees</a> or polytrees are DAGs formed by orienting the edges of trees (connected, acyclic undirected graphs).

<ul><li><a href="Rooted_tree" class="mw-redirect" title="Rooted tree">Rooted trees</a> are oriented trees in which all edges of the underlying undirected tree are directed either away from or towards the root (they are called, respectively, arborescences or out-trees, and in-trees.</li></ul></li></ul></li></ul></li></ul></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Digraphs_with_supplementary_properties">Digraphs with supplementary properties</h3></div>

<ul><li>Weighted directed graphs (also known as directed networks) are (simple) directed graphs with weights assigned to their arrows, similarly to <a href="Weighted_graph" class="mw-redirect" title="Weighted graph">weighted graphs</a> (which are also known as undirected networks or <a href="Weighted_network" title="Weighted network">weighted networks</a>).<a href="#cite_note-Chartrand-2">[2]</a>

<ul><li><a href="Flow_network" title="Flow network">Flow networks</a> are weighted directed graphs where two nodes are distinguished, a source and a sink.</li></ul></li>

<li><a href="Rooted_graph" title="Rooted graph">Rooted directed graphs</a> (also known as flow graphs) are digraphs in which a vertex has been distinguished as the root.

<ul><li><a href="Control-flow_graph" title="Control-flow graph">Control-flow graphs</a> are rooted digraphs used in computer science as a representation of the paths that might be traversed through a program during its execution.</li></ul></li>

<li><a href="Signal-flow_graph" title="Signal-flow graph">Signal-flow graphs</a> are directed graphs in which nodes represent system variables and branches (edges, arcs, or arrows) represent functional connections between pairs of nodes.</li>

<li><a href="Flow_graph_(mathematics)" title="Flow graph (mathematics)">Flow graphs</a> are digraphs associated with a set of linear algebraic or differential equations.</li>

<li><a href="State_diagram" title="State diagram">State diagrams</a> are <a href="Directed_multigraph" class="mw-redirect" title="Directed multigraph">directed multigraphs</a> that represent <a href="Finite-state_machine" title="Finite-state machine">finite-state machines</a>.</li>

<li><a href="Commutative_diagram" title="Commutative diagram">Commutative diagrams</a> are digraphs used in <a href="Category_theory" title="Category theory">category theory</a>, where the vertices represent (mathematical) objects and the arrows represent morphisms, with the property that all directed paths with the same start and endpoints lead to the same result by composition.</li>

<li>In the theory of <a href="Lie_group" title="Lie group">Lie groups</a>, a <a href="Quiver_(mathematics)" title="Quiver (mathematics)">quiver</a> Q is a directed graph serving as the domain of, and thus characterizing the shape of, a representation V defined as a <a href="Functor" title="Functor">functor</a>, specifically an object of the <a href="Functor_category" title="Functor category">functor category</a> FinVctKF(Q) where F(Q) is the <a href="Free_category" title="Free category">free category</a> on Q consisting of paths in Q and FinVctK is the category of finite-dimensional <a href="Vector_space" title="Vector space">vector spaces</a> over a <a href="Field_(mathematics)" title="Field (mathematics)">field</a> K. Representations of a quiver label its vertices with vector spaces and its edges (and hence paths) compatibly with <a href="Linear_map" title="Linear map">linear transformations</a> between them, and transform via <a href="Natural_transformation" title="Natural transformation">natural transformations</a>.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Basic_terminology">Basic terminology</h2></div>

An arc (x, y) is considered to be directed from x to y; y is called the head and x is called the tail of the arc; y is said to be a direct successor of x and x is said to be a direct predecessor of y. If a <a href="Path_(graph_theory)" title="Path (graph theory)">path</a> leads from x to y, then y is said to be a successor of x and reachable from x, and x is said to be a predecessor of y. The arc (y, x) is called the reversed arc of (x, y).

The <a href="Adjacency_matrix" title="Adjacency matrix">adjacency matrix</a> of a multidigraph with loops is the integer-valued <a href="Matrix_(mathematics)" title="Matrix (mathematics)">matrix</a> with rows and columns corresponding to the vertices, where a nondiagonal entry aij is the number of arcs from vertex i to vertex j, and the diagonal entry aii is the number of loops at vertex i. The adjacency matrix of a directed graph is a <a href="Logical_matrix" title="Logical matrix">logical matrix</a>, and is

unique up to permutation of rows and columns.

Another matrix representation for a directed graph is its <a href="Incidence_matrix" title="Incidence matrix">incidence matrix</a>.

See <a href="Glossary_of_graph_theory#direction" title="Glossary of graph theory">direction</a> for more definitions.

<div class="mw-heading mw-heading2"><h2 id="Indegree_and_outdegree">Indegree and outdegree</h2></div>

For a vertex, the number of head ends adjacent to a vertex is called the indegree of the vertex and the number of tail ends adjacent to a vertex is its outdegree (called <a href="Branching_factor" title="Branching factor">branching factor</a> in trees).

Let G = (V, E) and v ∈ V. The indegree of v is denoted deg−(v) and its outdegree is denoted deg+(v).

A vertex with deg−(v) = 0 is called a source, as it is the origin of each of its outgoing arcs. Similarly, a vertex with deg+(v) = 0 is called a sink, since it is the end of each of its incoming arcs.

The degree sum formula states that, for a directed graph,

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{v\in V}\deg ^{-}(v)=\sum _{v\in V}\deg ^{+}(v)=|E|.}</annotation>

</semantics>

</math><img src="./54746bb69917d1418094632650376ad5db6ecaff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:33.267ex; height:5.676ex;" alt="{\displaystyle \sum _{v\in V}\deg ^{-}(v)=\sum _{v\in V}\deg ^{+}(v)=|E|.}" loading="lazy"></dd></dl>

If for every vertex v ∈ V, deg+(v) = deg−(v), the graph is called a balanced directed graph.<a href="#cite_note-8">[8]</a>

<div class="mw-heading mw-heading2"><h2 id="Degree_sequence">Degree sequence</h2></div>

The degree sequence of a directed graph is the list of its indegree and outdegree pairs; for the above example we have degree sequence ((2, 0), (2, 2), (0, 2), (1, 1)). The degree sequence is a directed graph invariant so isomorphic directed graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a directed graph; in some cases, non-isomorphic digraphs have the same degree sequence.

The <a href="Digraph_realization_problem" title="Digraph realization problem">directed graph realization problem</a> is the problem of finding a directed graph with the degree sequence a given sequence of positive <a href="Integer" title="Integer">integer</a> pairs. (Trailing pairs of zeros may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the directed graph.) A sequence which is the degree sequence of some directed graph, i.e. for which the directed graph realization problem has a solution, is called a directed graphic or directed graphical sequence. This problem can either be solved by the <a href="Kleitman%E2%80%93Wang_algorithm" class="mw-redirect" title="Kleitman–Wang algorithm">Kleitman–Wang algorithm</a> or by the <a href="Fulkerson%E2%80%93Chen%E2%80%93Anstee_theorem" title="Fulkerson–Chen–Anstee theorem">Fulkerson–Chen–Anstee theorem</a>.

<div class="mw-heading mw-heading2"><h2 id="Directed_graph_connectivity">Directed graph connectivity</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Connectivity_(graph_theory)" title="Connectivity (graph theory)">Connectivity (graph theory)</a></div>

A directed graph is weakly connected (or just connected<a href="#cite_note-9">[9]</a>) if the undirected underlying graph obtained by replacing all directed edges of the graph with undirected edges is a <a href="Connectivity_(graph_theory)" title="Connectivity (graph theory)">connected graph</a>.

A directed graph is <a href="Strongly_connected" class="mw-redirect" title="Strongly connected">strongly connected</a> or strong if it contains a directed path from x to y (and from y to x) for every pair of vertices (x, y). The strong components are the maximal strongly connected subgraphs.

A connected <a href="Rooted_graph" title="Rooted graph">rooted graph</a> (or flow graph) is one where there exists a directed path to every vertex from a distinguished root vertex.

/* start https://en.wikipedia.org/ */

.mw-parser-output .div-col{margin-top:0.3em;column-width:30em}.mw-parser-output .div-col-small{font-size:90%}.mw-parser-output .div-col-rules{column-rule:1px solid #aaa}.mw-parser-output .div-col dl,.mw-parser-output .div-col ol,.mw-parser-output .div-col ul{margin-top:0}.mw-parser-output .div-col li,.mw-parser-output .div-col dd{page-break-inside:avoid;break-inside:avoid-column}

/* end https://en.wikipedia.org/ */

</style><div class="div-col" style="column-width: 30em;">

<ul><li><a href="Binary_relation" title="Binary relation">Binary relation</a> – Relationship between elements of two sets</li>

<li><a href="Coates_graph" title="Coates graph">Coates graph</a> – A mathematical graph for solution of linear equations</li>

<li><a href="DGML" title="DGML">Directed Graph Markup Language</a></li>

<li><a href="DRAKON" title="DRAKON">DRAKON flowchart</a> – Algorithm mapping tool</li>

<li><a href="Flow_chart" class="mw-redirect" title="Flow chart">Flow chart</a> – Diagram that represents a workflow or processPages displaying short descriptions of redirect targets</li>

<li><a href="Globular_set" title="Globular set">Globular set</a></li>

<li><a href="Glossary_of_graph_theory" title="Glossary of graph theory">Glossary of graph theory</a></li>

<li><a href="Graph_database" title="Graph database">Graph database</a> – Database using graph structures for queries</li>

<li><a href="Graph_Style_Sheets" title="Graph Style Sheets">Graph Style Sheets</a> – Framework in mathematics and computing</li>

<li><a href="Graph_theory" title="Graph theory">Graph theory</a> – Area of discrete mathematics</li>

<li><a href="Graph_(abstract_data_type)" title="Graph (abstract data type)">Graph (abstract data type)</a> – Abstract data type in computer science</li>

<li><a href="Network_theory" title="Network theory">Network theory</a> – Study of graphs as a representation of relations between discrete objects</li>

<li><a href="Orientation_(graph_theory)" title="Orientation (graph theory)">Orientation (graph theory)</a> – Assigning directions to the edges of an undirected graph</li>

<li><a href="Preorder" title="Preorder">Preorder</a> – Reflexive and transitive binary relation</li>

<li><a href="Topological_sorting" title="Topological sorting">Topological sorting</a> – Node ordering for directed acyclic graphs</li>

<li><a href="Transpose_graph" title="Transpose graph">Transpose graph</a> – Directed graph with reversed edges</li>

<li><a href="Vertical_constraint_graph" class="mw-redirect" title="Vertical constraint graph">Vertical constraint graph</a></li>

<li><a href="Zero-weight_cycle_problem" title="Zero-weight cycle problem">Zero-weight cycle problem</a></li></ul></div>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> <a href="#CITEREFBang-JensenGutin2000">Bang-Jensen & Gutin (2000)</a>. <a href="#CITEREFBang-JensenGutin2018">Bang-Jensen & Gutin (2018)</a>, Chapter 1.<a href="#CITEREFDiestel2005">Diestel (2005)</a>, Section 1.10. <a href="#CITEREFBondyMurty1976">Bondy & Murty (1976)</a>, Section 10.

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFChartrand1977" class="citation book cs1">Chartrand, Gary (1977). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=rYuToT7vHbMC&q=Introductory%20Graph%20Theory&pg=PP1">Introductory Graph Theory</a>. Courier Corporation. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780486247755</bdi>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230204155556/https://books.google.com/books?id=rYuToT7vHbMC&q=Introductory%20Graph%20Theory&pg=PP1">Archived</a> from the original on 2023-02-04. Retrieved 2020-10-02.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <a href="#CITEREFBang-JensenGutin2018">Bang-Jensen & Gutin (2018)</a>, Chapter 7 by Yeo.

</li>

<li id="cite_note-Bang-Jensen_2018-4">^ <a href="#cite_ref-Bang-Jensen_2018_4-0">a</a> <a href="#cite_ref-Bang-Jensen_2018_4-1">b</a> <a href="#CITEREFBang-JensenGutin2018">Bang-Jensen & Gutin (2018)</a>, Chapter 2 by Bang-Jensen and Havet.

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <a href="#CITEREFBang-JensenGutin2018">Bang-Jensen & Gutin (2018)</a>, Chapter 8 by Galeana-Sanchez and Hernandez-Cruz.

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <a href="#CITEREFDiestel2005">Diestel (2005)</a>, Section 1.10.

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <a href="#CITEREFBang-JensenGutin2018">Bang-Jensen & Gutin (2018)</a>, Chapter 3 by Gutin.

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFSatyanarayanaPrasad" class="citation cs2">Satyanarayana, Bhavanari; Prasad, Kuncham Syam, Discrete Mathematics and Graph Theory, PHI Learning Pvt. Ltd., p. 460, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-81-203-3842-5</bdi></cite>; <cite id="CITEREFBrualdi2006" class="citation cs2">Brualdi, Richard A. (2006), <a rel="nofollow" class="external text" href="https://archive.org/details/combinatorialmat0000brua/page/51">Combinatorial Matrix Classes</a>, Encyclopedia of Mathematics and Its Applications, vol. 108, Cambridge University Press, p. <a rel="nofollow" class="external text" href="https://archive.org/details/combinatorialmat0000brua/page/51">51</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-86565-4</bdi></cite>.

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <a href="#CITEREFBang-JensenGutin2000">Bang-Jensen & Gutin (2000)</a> p. 19 in the 2007 edition; p. 20 in the 2nd edition (2009).

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li><cite id="CITEREFBang-JensenGutin2000" class="citation cs2">Bang-Jensen, Jørgen; Gutin, Gregory (2000), <a rel="nofollow" class="external text" href="http://www.cs.rhul.ac.uk/books/dbook/">Digraphs: Theory, Algorithms and Applications</a>, <a href="Springer_Science%2BBusiness_Media" title="Springer Science+Business Media">Springer</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-85233-268-9</bdi></cite>(the corrected 1st edition of 2007 is now freely available on the authors' site; the 2nd edition appeared in 2009 <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>1-84800-997-6</bdi>).</li>

<li><cite id="CITEREFBang-JensenGutin2018" class="citation cs2">Bang-Jensen, Jørgen; Gutin, Gregory (2018), Classes of Directed Graphs, <a href="Springer_International_Publishing_AG" class="mw-redirect" title="Springer International Publishing AG">Springer</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3319718408</bdi></cite>.</li>

<li><cite id="CITEREFBondyMurty1976" class="citation cs2"><a href="John_Adrian_Bondy" title="John Adrian Bondy">Bondy, John Adrian</a>; <a href="U._S._R._Murty" title="U. S. R. Murty">Murty, U. S. R.</a> (1976), <a rel="nofollow" class="external text" href="https://archive.org/details/graphtheorywitha0000bond">Graph Theory with Applications</a>, North-Holland, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-444-19451-7</bdi></cite>.</li>

<li><cite id="CITEREFDiestel2005" class="citation cs2"><a href="Reinhard_Diestel" title="Reinhard Diestel">Diestel, Reinhard</a> (2005), <a rel="nofollow" class="external text" href="http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/">Graph Theory</a> (3rd ed.), <a href="Springer_Science%2BBusiness_Media" title="Springer Science+Business Media">Springer</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-26182-6</bdi></cite> (the electronic 3rd edition is freely available on author's site).</li>

<li><cite id="CITEREFHararyNormanCartwright1965" class="citation cs2"><a href="Frank_Harary" title="Frank Harary">Harary, Frank</a>; Norman, Robert Z.; Cartwright, Dorwin (1965), Structural Models: An Introduction to the Theory of Directed Graphs, New York: Wiley</cite>.</li>

<li><a rel="nofollow" class="external text" href="https://oeis.org/A000273">Number of directed graphs (or directed graphs) with n nodes</a> from <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">On-Line Encyclopedia of Integer Sequences</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">Wikimedia Commons has media related to <a href="https://commons.wikimedia.org/wiki/Category:Directed_graphs" class="extiw external" title="commons:Category:Directed graphs">Directed graphs</a>.</div></div>

</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1038841319">

/* start https://en.wikipedia.org/ */

.mw-parser-output .tooltip-dotted{border-bottom:1px dotted;cursor:help}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox authority-control" aria-labelledby="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q1137726#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata1777" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Authority_control_databases_frameless&#124;text-top&#124;10px&#124;alt=Edit_this_at_Wikidata&#124;link=https&#58;//www.wikidata.org/wiki/Q1137726#identifiers&#124;class=noprint&#124;Edit_this_at_Wikidata1777" style="font-size:114%;margin:0 4em">Authority control databases </div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">National</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4156815-1">Germany</a></li><li><a rel="nofollow" class="external text" href="https://id.loc.gov/authorities/sh85038262">United States</a></li><li><a rel="nofollow" class="external text" href="https://catalogue.bnf.fr/ark:/12148/cb119847650">France</a></li><li><a rel="nofollow" class="external text" href="https://data.bnf.fr/ark:/12148/cb119847650">BnF data</a></li><li><a rel="nofollow" class="external text" href="https://aleph.nkp.cz/F/?func=find-c&local_base=aut&ccl_term=ica=ph139314&CON_LNG=ENG">Czech Republic</a></li><li><a rel="nofollow" class="external text" href="https://www.nli.org.il/en/authorities/987007555293505171">Israel</a></li></ul></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"><ul><li><a rel="nofollow" class="external text" href="https://lux.collections.yale.edu/view/concept/109c374f-ffa4-40b0-82d8-f54f9e1988e2">Yale LUX</a></li></ul></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-08-08" href="https://en.wikipedia.org/wiki/?title=Directed_graph&oldid=1304785500">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>